#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <bitset>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <unordered_set>

#include <functional>
#include <climits>
#include <algorithm>
#include <iostream>	 // std::cout
#include <algorithm> // std::sort
#include <vector>

using namespace std;

struct TreeNode
{
	int value;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : value(x), left(NULL), right(NULL) {}
};

struct ListNode
{
	int value;
	ListNode *next;
	//ListNode(int x) :value(x), next(NULL) {}
};

// LeetCode 100

// 01 Two Sum(E)
//先使用排序，然后取数值的头和尾，相加，如果大于sum就把尾向前移，如果小于sum，把头向前移动，直到等于sum
// 双指针

// 02 Add two numbers(M)
// 有两个链表，它们表示逆序的两个非负数。计算出两个数的和之后，同样逆序输出作为一个链表，需要注意一点：有进位
// Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
//	Output : 7 -> 0 -> 8
// 这道并不是什么难题，算法很简单，链表的数据类型也不难，就是建立一个新链表，然后把输入的两个链表从头往后撸，每两个相加，添加一个新节点到新链表后面。
// 为了避免两个输入链表同时为空，我们建立一个 dummy 结点，将两个结点相加生成的新结点按顺序加到 dummy 结点之后，由于 dummy 结点本身不能变，所以用一个指针 cur 来指向新链表的最后一个结点。好，
// 可以开始让两个链表相加了，这道题好就好在最低位在链表的开头，所以可以在遍历链表的同时按从低到高的顺序直接相加。while 循环的条件两个链表中只要有一个不为空行，由于链表可能为空，
// 所以在取当前结点值的时候，先判断一下，若为空则取0，否则取结点值。然后把两个结点值相加，同时还要加上进位 carry。然后更新 carry，直接 sum/10 即可，然后以 sum%10 为值建立一个新结点，连到 cur 后面，
// 然后 cur 移动到下一个结点。之后再更新两个结点，若存在，则指向下一个位置。while 循环退出之后，最高位的进位问题要最后特殊处理一下，若 carry 为1，则再建一个值为1的结点

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
{
	ListNode *dummy = new ListNode(-1), *cur = dummy;
	int carry = 0;
	while (l1 || l2)
	{
		int val1 = l1 ? l1->val : 0;
		int val2 = l2 ? l2->val : 0;
		int sum = val1 + val2 + carry;
		carry = sum / 10;
		cur->next = new ListNode(sum % 10);
		cur = cur->next;
		if (l1)
			l1 = l1->next;
		if (l2)
			l2 = l2->next;
	}
	if (carry)
		cur->next = new ListNode(1);
	return dummy->next;
}

// 03 longest substring without repeating characters(M)
// 最长无重复子串 (注意这里是子串，不是子序列，所以必须是连续的)
//滑动窗口

int lengthOfLongestSubstring(string s)
{
	int res = 0;
	unordered_map<char, int> mp;
	for (int i = 0; i < s.size(); i++)
	{
		mp[s[i]]++;
	}
	for (int i = 0; i < s.size(); i++)
	{
		if (mp[s[i]] == 1)
		{
			res++;
		}
	}
	return res;
}

/*
int main() {
	string s = "ewwwewwerra";
	cout << lengthOfLongestSubstring(s) << endl;

	return 0;
}
*/

// 04 median of two sorted arrays(H)
//将两个数组合并，并排序，然后去合并后数组的中位数

// 05 longest palindromic substring(M)
//最大回文子串：分两种情况，回文子串长度为偶数和奇数：奇数的话直接向两边搜索，偶数的话和下一个数一起向两边搜索
void search_Palindrome(string s, int left, int right, int &start, int &maxLen)
{
	while (left >= 0 && right <= s.size() && (s[left] == s[right]))
	{
		left--;
		right++;
	}
	if (maxLen < (right - left - 1))
	{
		start = left + 1;
		maxLen = right - left - 1;
	}
}

string Longest_Palindrome(string s)
{
	if (s.size() < 2)
	{
		return s;
	}
	int maxLEN = 0;
	int start = 0;
	for (int i = 0; i < s.size() - 1; i++)
	{
		search_Palindrome(s, i, i, start, maxLEN);
		search_Palindrome(s, i, i + 1, start, maxLEN);
	}
	return s.substr(start, maxLEN);
}

/*
int main() {
	string s = "wddw";
	cout<<Longest_Palindrome(s)<<endl;
	return 0;
}
*/

// 06 Regular Expression Matching (H)
//正则表达式匹配：递归&分情况讨论
// 动态规划

// bool isMatch(string s, string p)
// {
// 	if (p.empty())
// 		return s.empty();
// 	if (p.size() == 1)
// 	{
// 		return (s.size() == 1 && (s[0] == p[0] || p[0] == '.'));
// 	}
// 	if (p[1] != '*')
// 	{
// 		if (s.empty())
// 			return false;
// 		return (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
// 	}
// 	while (!s.empty() && (s[0] == p[0] || p[0] == '.'))
// 	{
// 		if (isMatch(s, p.substr(2)))
// 			return true;
// 		s = s.substr(1);
// 	}
// 	return isMatch(s, p.substr(2));
// }

// // step_1
// bool isMatch(string text, string pattern)
// {
// 	if (text.size() != pattern.size())
// 		return false;
// 	for (int j = 0; j < pattern.size(); j++)
// 	{
// 		if (pattern[j] != text[j])
// 			return false;
// 	}
// 	return true;
// }

// // step_2
// bool isMatch(string text, string pattern)
// {
// 	int i = 0; // text 的索引位置
// 	int j = 0; // pattern 的索引位置
// 	while (j < pattern.size())
// 	{
// 		if (i >= text.size())
// 			return false;
// 		if (pattern[j++] != text[i++])
// 			return false;
// 	}
// 	// 相等则说明完成匹配
// 	return j == text.size();
// }

// // step_3
// def isMatch(text, pattern) -> bool:
//     if pattern is empty: return (text is empty?)
//     first_match = (text not empty) and pattern[0] == text[0]
//     return first_match and isMatch(text[1:], pattern[1:])

// // step_4  // 处理点号「.」通配符
// def isMatch(text, pattern) -> bool:
//     if not pattern: return not text
//     first_match = bool(text) and pattern[0] in
// {
// 	text[0], '.'
// }
// if
// 	len(pattern) >= 2 and pattern[1] == '*' :
// #发现 '*' 通配符
// 		else : return first_match
// 			and isMatch(text [1:], pattern [1:])

// 					// 处理「*」通配符
// 					if len(pattern) >= 2 and
// 			pattern[1] == '*' : return isMatch(text, pattern [2:]) or
// 		first_match and isMatch(text [1:], pattern)
// #解释：如果发现有字符和 '*' 结合，
// #或者匹配该字符 0 次，然后跳过该字符和 '*'
// #或者当 pattern[0] 和 text[0] 匹配后，移动 text

// 						// # 暴力递归
// 						def isMatch(text, pattern)
// 							->bool : if not pattern : return not text

// 													  first = bool(text) and pattern[0] in
// 	{
// 		text[0], '.'
// 	}

// if
// 	len(pattern) >= 2 and pattern[1] == '*' : return isMatch(text, pattern [2:]) or
// 		first and isMatch(text [1:], pattern) else : return first and isMatch(text [1:], pattern [1:])

// 07 container with most water(M)
// 双指针
// // 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
// 我们可以用两个指针，一个指针left指向开始，另一个right指向结尾，如果left木板比right木板矮，那就让left指针右移；
// 如果left木板比right木板高，那么right指针左移。为什么不是left木板比right木板高就右移left呢？因为木桶效应，盛水量多少，取决于那块最短的板
int maxArea(vector<int> &height)
{
	int left = 0;
	int right = height.size();
	int res = 0;
	while (left < right)
	{
		res = max(res, min(height[left], height[right]) * (left - right));
		height[left] < height[right] ? left++ : right--; // 排除最短的板
	}
	return res;
}

// 08 three sum(M)
// two sum
// 先排序
vector<int> twoSum(vector<int> &nums, int target, int start, int end)
{
	sort(nums.begin(), nums.end());
	vector<int> res;
	int left = start;
	int right = end;
	while (left <= right)
	{
		if (nums[left] + nums[right] > target)
		{
			right--;
		}
		else if (nums[left] + nums[right] > target)
		{
			left++;
		}
		else
		{
			res.push_back(nums[left]);
			res.push_back(nums[right]);
		}
	}
	return res;
}

vector<int> three_Sum(vector<int> &nums, int target)
{
	vector<int> res_three;
	vector<int> res_two_sum;
	sort(nums.begin(), nums.end());
	for (int i = 0; i < nums.size(); i++)
	{
		int start = i;
		int end = nums.size() - 1;
		// 两俩sum之后，找第三个
		res_two_sum = (twoSum(nums, target - nums[i], start, end));
		if (!res_two_sum.empty())
		{
			res_three.push_back(nums[i]);
			res_three.push_back(res_two_sum[0]);
			res_three.push_back(res_two_sum[1]);
			break;
		}
	}
	return res_three;
}

// 09
// 求电话号码的字母组合，即数字2到9中每个数字可以代表若干个字母，然后给一串数字，求出所有可能的组合
// 建立字典：每个数字代表的字符串，然后递归：DFS
vector<string> letterCombinations(string digits)
{
	if (digits.empty())
		return {};
	vector<string> res;
	vector<string> dict{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
	letterCombinationsDFS(digits, dict, 0, "", res);
	return res;
}
void letterCombinationsDFS(string &digits, vector<string> &dict, int level, string out, vector<string> &res)
{
	if (level == digits.size())
	{
		res.push_back(out);
		return;
	}
	string str = dict[digits[level] - '0'];
	for (int i = 0; i < str.size(); ++i)
	{
		letterCombinationsDFS(digits, dict, level + 1, out + str[i], res);
	}
}

// 10 remove Nth node from end of list(M)
// 先找到第N个链表，快慢两个指针
void removeNthFromEnd(ListNode *head, int n)
{
	ListNode *fast = head;
	;
	ListNode *slow = head;
	for (int i = 0; i <= n; i++)
	{
		fast = fast->next;
	}
	while (fast)
	{
		fast = fast->next;
		slow = slow->next;
	}
	slow->next = slow->next->next;
}

// 11 valid parenthese 验证括号(E)
// 使用栈，如果为左括号，就将其入栈，如果遇到右括号，就拿出栈顶元素比较
bool isValid(string s)
{
	stack<char> parenthese;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == '(' || s[i] == '[' || s[i] == '{')
		{
			parenthese.push(s[i]);
		}
		else
		{
			if (parenthese.empty())
			{
				return false;
			}
			if (s[i] == ')' && parenthese.top() != '(')
				return false;
			if (s[i] == '}' && parenthese.top() != '{')
				return false;
			if (s[i] == ']' && parenthese.top() != '[')
				return false;
			parenthese.pop();
		}
	}
	return parenthese.empty();
}

// 12 Merge two sorted list(E)
// 递归
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
	ListNode *res = NULL;
	if (l1->value > l2->value)
	{
		res = l1;
		mergeTwoLists(l1->next, l2);
	}
	else
	{
		res = l2;
		mergeTwoLists(l1, l2->next);
	}
	return res;
}

// 13 generate parenthese(M)
// 这道题给定一个数字n，让生成共有n个括号的所有正确的形式，对于这种列出所有结果的题首先还是考虑用递归Recursion来解

vector<string> result;
vector<string> generateParenthesis(int n)
{
	generate(0, 0, "", n);
	return result;
}
void generate(int left, int right, string s, int n)
{
	if (right == n)
	{
		result.push_back(s);
	}
	else
	{
		if (left < n)
		{
			generate(left + 1, right, s + "(", n);
		}
		if (right < left)
		{
			generate(left, right + 1, s + ")", n);
		}
	}
}

// 14 merge k sorted list(H)
// ListNode* mergeTwoLists(ListNode *l1, ListNode *l2)
// 分治
ListNode *mergeKLists(vector<ListNode *> &lists)
{
	int n = lists.size();
	while (n > 1)
	{
		int k = (n + 1) / 2;
		for (int i = 0; i < n / 2; i++)
		{
			mergeTwoLists(lists[i], lists[i + k]);
		}
		n = k;
	}
	return lists[0];
}

// 15 longest valid parenteses(H)
// 最长有效括号: 栈和DP
int longestValidParentheses(string s)
{
	if (s.length() == 0)
		return 0;
	int res = 0;
	stack<int> st;
	st.push(-1);
	for (int i = 0; i < s.length(); ++i)
	{
		if (s[i] == '(')
		{
			st.push(i);
		}
		else
		{
			st.pop();
			if (!st.empty())
			{
				res = max(res, i - st.top());
			}
			else
			{
				st.push(i);
			}
		}
	}
	return res;
}

//16 search in rotated sorted array(M)
//二分搜索，left,mid,right
int search(vector<int> &nums, int target)
{
	int len = nums.size(), left = 0, right = len - 1;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (nums[mid] == target)
			return mid;
		if (nums[mid] >= nums[0])
		{
			if (target < nums[mid] && target >= nums[0])
				right = mid - 1;
			else
				left = mid + 1;
		}
		else
		{
			if (target > nums[mid] && target < nums[0])
				left = mid + 1;
			else
				right = mid - 1;
		}
	}
	return -1;
}

//17 find first and last postion of element in sorted array(m)
//两遍二分查找 binary search
//一遍二分查找知找左边  // 一遍二分查找知找右边
vector<int> searchRange(vector<int> nums, int target)
{
	vector<int> res;
	int ll = 0;
	int lr = nums.size() - 1;
	int mid = 0;
	while (ll <= lr)
	{
		mid = ll + (lr - ll) / 2;
		if (nums[mid] > target)
		{
			lr = mid - 1;
		}
		else
		{
			ll = mid + 1;
		}
	}
	int rl = 0;
	int rr = nums.size() - 1;
	while (rl <= rr)
	{
		int mid = rl + (rr - rl) / 2;
		if (nums[mid] <= target)
		{
			rl = mid + 1;
		}
		else
		{
			rr = mid - 1;
		}
	}

	if (ll > rr)
	{
		res[0] = ll;
		res[1] = rr;
	}
	return res;
}

// 18 search insert position (E)
//二分查找
int searchInsert(vector<int> nums, int target)
{
	int ll = 0;
	int lr = nums.size() - 1;
	int mid = 0;
	while (ll <= lr)
	{
		mid = ll + (lr - ll) / 2;
		if (nums[mid] > target)
		{
			lr = mid - 1;
		}
		else if (nums[mid] < target)
		{
			ll = mid + 1;
		}
		else
		{
			return mid;
		}
	}
}

//19 combination sum(M)
// 组合之和  // 回溯框架  // 参考全排序
// Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), 
// find all unique combinations in candidates where the candidate numbers sums to targe
// 先排序再递归
vector<vector<int>> combinationSum(vector<int> &candidates, int target)
{
	vector<vector<int>> res;
	sort(candidates.begin(), candidates.end());

	for (int i = 0; i < candidates.size(); i++)
	{
		if (candidates[i] > target)
		{
			break;
		}
		else if (candidates[i] == target)
		{
			res.push_back({candidates[i]});
			continue;
		}

		vector<int> remaining = vector<int>(candidates.begin() + 1, candidates.end());
		vector<vector<int>> tmp = combinationSum(remaining, target - candidates[i]);
		for (auto a : tmp)
		{
			a.insert(a.begin(), candidates[i]);
			res.push_back(a);
		}
	}
	return res;
}

//trapping rain water(H)
//1. 从左往右扫描一遍，对于每一个坐标，求取左边最大值。
//2. 从右往左扫描一遍，对于每一个坐标，求最大右值。
//3. 再扫描一遍，求取容积并加和。volume[i] = [min(left[i], right[i]) - A[i]] * 1，这里的1是宽度，如果the width of each bar is 2, 那就要乘以2了
//front & back,   start &end
//
int trap(vector<int> A)
{
	int res = 0;
	int max;
	int i = 0;
	int j = 0;
	vector<int> left;
	vector<int> right;

	for (i = 0, max = A.front(), left[0] = A.front(); i < A.size(); i++)
	{
		if (A[i] < max)
		{
			left[i] = max;
		}
		else
		{
			left[i] = A[i];
			max = A[i];
		}
	}

	for (j = A.size() - 2, max = A.back(), right.front() = A.back(); j >= 0; j--)
	{
		if (A[i] < max)
		{
			right[i] = max;
		}
		else
		{
			right[i] = A[i];
			max = A[i];
		}
	}

	int volume = 0;
	for (int i = 0; i < A.size() - 2; i++)
	{
		volume = min(left[i], right[i]) - A[i];
		if (volume > 0)
		{
			volume += volume;
		}
	}
	return volume;
}

//21 permutation (M)
//全排序
// 回溯的框架
void permutation_DFS(vector<int> &num, int start, vector<vector<int>> res)
{
	if (start >= num.size())
	{
		res.push_back(num);
	}
	for (int i = start; i < num.size(); i++)
	{
		swap(num[start], num[i]);
		permutation_DFS(num, start + 1, res);
		swap(num[start], num[i]);
	}
}

vector<vector<int>> Permutation(vector<int> &num)
{
	vector<vector<int>> res;
	permutation_DFS(num, 0, res);
	return res;
}

//22 Rotate image(M)
//先沿对角线旋转，在沿x轴旋转
void rotate(vector<vector<int>> &matrix)
{
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	int len = matrix[0].size();
	for (int i = 0; i < len - 1; i++)
	{
		for (int j = 0; j < len - i; j++)
		{
			swap(matrix[i][j], matrix[len - 1 - j][len - 1 - i]);
		}
	}

	for (int i = 0; i < len / 2; i++)
	{
		for (int j = 0; j < len; j++)
		{
			swap(matrix[i][j], matrix[len - i - 1][j]);
		}
	}
}

//23 Group anagrams(M)
//错位词就是两个字符串中字母出现的次数都一样，只是位置不同，比如abc，bac, cba等它们就互为错位词
//把错位词，排序后都是一样的，使用map
vector<vector<string>> groupAnagrams(vector<string> &strs)
{
	vector<vector<string>> res;
	unordered_map<string, vector<string>> m;
	for (string sr : strs)
	{
		string temp = sr;
		sort(sr.begin(), sr.end());
		m[sr].push_back(sr);
	}

	for (auto a : m)
	{
		res.push_back(a.second);
	}
	return res;
}

//24 maximum subarray(E)
// dp[i] = max(dp[i-1] + nums[i], nums[i])
// Given an integer array nums, find the contiguous subarray (containing at least one number)
//  which has the largest sum and return its sum
int maxSubArray(vector<int> &nums)
{
	int res = INT_MIN, curSum = 0;
	for (int num : nums)
	{
		curSum = max(curSum + num, num);
		res = max(res, curSum);
	}
	return res;
}

//25 Jump game(M)
// greedy  or DP
// 一维 DP
bool canJump(vector<int> &nums)
{
	int n = nums.size(), reach = 0;
	for (int i = 0; i < n; ++i)
	{
		if (i > reach || reach >= n - 1)
			break;
		reach = max(reach, i + nums[i]);
	}
	return reach >= n - 1;
}

//26 Merge intervals (M)
struct Interval
{
	int start;
	int end;
	Interval() : start(0), end(0) {}
	Interval(int s, int e) : start(s), end(e) {}
};

class Solution
{
public:
	vector<Interval> merge(vector<Interval> &intervals)
	{
		int n = intervals.size();
		vector<Interval> res;
		vector<int> starts, ends;
		for (int i = 0; i < n; ++i)
		{
			starts.push_back(intervals[i].start);
			ends.push_back(intervals[i].end);
		}
		sort(starts.begin(), starts.end());
		sort(ends.begin(), ends.end());
		for (int i = 0, j = 0; i < n; ++i)
		{
			if (i == n - 1 || starts[i + 1] > ends[i])
			{
				res.push_back(Interval(starts[j], ends[i]));
				j = i + 1;
			}
		}
		return res;
	}
};

//26 Flatten binary tree to linked list(M)
// https://www.cnblogs.com/grandyang/p/4293853.html
//将二叉树转换成链表
//这道题要求把二叉树展开成链表，根据展开后形成的链表的顺序分析出是使用先序遍历，那么只要是数的遍历就有递归和非递归的两种方法来求解，
// 这里我们也用两种方法来求解。首先来看递归版本的，思路是先利用DFS的思路找到最左子节点，然后回到其父节点，把其父节点和右子节点断开，
// 将原左子结点连上父节点的右子节点上，然后再把原右子节点连到新右子节点的右子节点上，然后再回到上一父节点做相同操作
// Recursion
class Solution_26
{
public:
	void flatten(TreeNode *root)
	{
		if (!root)
			return;
		if (root->left)
			flatten(root->left);
		if (root->right)
			flatten(root->right);
		TreeNode *tmp = root->right;
		root->right = root->left;
		root->left = NULL;
		while (root->right)
			root = root->right;
		root->right = tmp;
	}
};

//28  Unique path(M)
// 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）
// 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）
// 问总共有多少条不同的路径？

// 递归
vector<vector<int>> f_;
int uniquePaths(int m, int n)
{
	if (m < 0 || n < 0)
		return 0;
	if (m == 1 && n == 1)
		return 1;
	if (f_[m][n] > 0)
		return f_[m][n];
	int left_paths = uniquePaths(m - 1, n);
	int top_paths = uniquePaths(m, n - 1);
	f_[m][n] = left_paths + top_paths;
	return f_[m][n];
}

// 二维 DP
int uniquePaths(int m, int n)
{
	DP[m][n];
	if (m < 0 || n < 0)
		return 0;
	if (m == 1 && n == 1)
		DP[m][n] = 1;

	for (int i = 2; i < m; i++)
	{
		for (int j = 2; j < n; j++)
		{
			DP[m][n] = (DP[m][n - 1] + 1 + DP[m - 1][n] + 1);
		}
	}

	return f_[m][n];
}

//29 minimum path sum(M)
// 这道题给了我们一个只有非负数的二维数组，让找一条从左上到右下的路径，使得路径和最小，限定了每次只能向下或者向右移动

// 二维的DP

// 一个常见的错误解法就是每次走右边或下边数字中较小的那个，这样的贪婪算法获得的局部最优解不一定是全局最优解，因此是不行的。实际上这道题跟之前那道 Dungeon Game 没有什么太大的区别，
// 都需要用动态规划 Dynamic Programming 来做，这应该算是 DP 问题中比较简单的一类，
// 我们维护一个二维的 dp 数组，其中 dp[i][j] 表示到达当前位置的最小路径和。接下来找状态转移方程，因为到达当前位置 (i, j)  
// 只有两种情况，要么从上方 (i-1, j) 过来，要么从左边 (i, j-1) 过来，
// 我们选择 dp 值较小的那个路径，即比较 dp[i-1][j] 和 dp[i][j-1]，将其中的较小值加上当前的数字 grid[i][j]，就是当前位置的 dp 值了。
// 但是有些特殊情况要提前赋值，比如起点位置，直接赋值为 grid[0][0]，还有就是第一行和第一列，其中第一行的位置只能从左边过来，
// 第一列的位置从能从上面过来，所以这两行要提前初始化好，
// 然后再从 (1, 1) 的位置开始更新到右下角即可，反正难度不算大，
int minPathSum(vector<vector<int>> &grid)
{
	int m = grid.size();
	int n = grid[0].size();
	vector<vector<int>> dp;
	dp[0][0] = grid[0][0];
	for (int i = 1; i < m; ++i)
		dp[i][0] = grid[i][0] + dp[i - 1][0];
	for (int i = 1; i < n; ++i)
		dp[0][i] = grid[0][i] + dp[0][i - 1];
	for (int i = 1; i < m; ++i)
	{
		for (int j = 1; j < n; ++j)
		{
			dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
		}
	}
	return dp[m - 1][n - 1];
}

//30 climbing stairs(M)
// 跟斐波那契数列非常相似，假设梯子有n层，那么如何爬到第n层呢，因为每次只能爬1或2步，那么爬到第n层的方法要么是从第 n-1 层一步上来的，
// 要不就是从 n-2 层2步上来的，
// 所以递推公式非常容易的就得出了：dp[n] = dp[n-1] + dp[n-2]

// 递归
int climbStairsRecur(int n)
{
	if (n == 1)
		return 1;
	if (n == 2)
		return 2;
	return climbStairsRecur(n - 1) + climbStairsRecur(n - 2);
}

// 一维 DP
int climbStairs(int n)
{
	if (n <= 1)
		return 1;
	vector<int> dp(n);
	dp[0] = 1;
	dp[1] = 2;
	for (int i = 2; i < n; ++i)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp.back();
}

//31 Edit distance (H)
// 编辑距离
// 二维DP
int minDistance(string s1, string s2)
{
	int m = s1.size();
	int n = s2.size();
	vector<vector<int>> dp(m + 1, vector<int>(n + 1));
	for (int i = 1; i <= m; i++)
		dp[i][0] = i; // base case: 当s2为空，s1需要删除所有字符才能与s2相等
	for (int j = 1; j <= n; j++)
		dp[0][j] = j; // base case: 当s1为空, s1需要不断插入新字符才能与s2相等
	//自底向上求解
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (s1[i - 1] == s2[j - 1])
			{ // 两个字符串当前的字符一样  // 啥都别做（skip）i, j 同时向前移动
				dp[i][j] = dp[i - 1][j - 1];
			}
			else										// 两个字符串当前的字符不同
														//使得s1[0:i]和s2[0:j]相同的最短编辑距离可通过插入，删除或替换三种操作其中一种得到
				dp[i][j] = min({dp[i - 1][j] + 1,		// 删除s1[i]这个字符
								dp[i][j - 1] + 1,		// 在s1[i]后面加一个和s2[j]相同的字符  // 我直接在 s1[i] 插入一个和 s2[j] 一样的字符,那么 s2[j] 就被匹配了，前移 j，继续跟 i 对比,别忘了操作数加一
								dp[i - 1][j - 1] + 1}); // 将s1[i]的字符替换为s2[j]的字符
		}
	}
	//储存着整个 s1 和 s2 的最小编辑距离
	return dp[m][n];
}

// 32 sort colours(M)
// Input: [2,0,2,1,1,0]
// Output: [0,0,1,1,2,2]
//count[A[i]]
// 这道题的本质还是一道排序的题，题目中给出提示说可以用计数排序，需要遍历数组两遍，那么先来看这种方法，因为数组中只有三个不同的元素，所以实现起来很容易
// 首先遍历一遍原数组，分别记录 0，1，2 的个数
// 然后更新原数组，按个数分别赋上 0，1，2
void sortColors(int A[], int n)
{
	int count[2] = {};
	for (int i = 0; i < n; i++)
	{
		count[A[i]]++;
	}
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < count[A[i]]; j++)
		{
			A[j] = i;
		}
	}
}

// 使用双指针法
void sortColors(vector<int> &nums)
{
	int red = 0, blue = (int)nums.size() - 1;
	for (int i = 0; i <= blue; ++i)
	{
		if (nums[i] == 0)
		{
			swap(nums[i], nums[red++]);
		}
		else if (nums[i] == 2)
		{
			swap(nums[i--], nums[blue--]);
		}
	}
}

//33 minimum window substring (H)
// 题目描述:
// 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
// 示例:
// 输入: S = "ADOBECODEBANC", T = "ABC"
// 输出: "BANC"

// 滑动窗口
// 双指针的框架
int left = 0;
int right = 0;
string source;
string window;
int res_length = source.size();
while (right < source.size())
{
	right++;
	window.add(source[right]);
	if (window is valid)
	{
		res_length = min(res_length, window.size());
		window.remove(source[left]);
		left++;
	}
}

// 34 subsets (M)
// 子集合
// Non-recursion
// Given a set of distinct integers, S, return all possible subsets.
// Note:
// Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets.
// For example,
// If S = [1,2,3], a solution is:
// [
//   [3],
//   [1],
//   [2],
//   [1,2,3],
//   [1,3],
//   [2,3],
//   [1,2],
//   []
// ]

vector<vector<int>> subsets(vector<int> &S)
{
	vector<vector<int>> res(1);
	sort(S.begin(), S.end());
	for (int i = 0; i < S.size(); ++i)
	{
		int size = res.size();
		for (int j = 0; j < size; ++j)
		{ // 1个，2个，3个...
			res.push_back(res[j]);
			res.back().push_back(S[i]);
		}
	}
	return res;
}

// 35 word search(M)
// 如果二维数组board的当前字符和目标字符串word对应的字符相等，则对其上下左右四个邻字符分别调用DFS的递归函数，只要有一个返回true，
// 那么就表示可以找到对应的字符串，否则就不能找到
// 这道题是典型的深度优先遍历 DFS 的应用，原二维数组就像是一个迷宫，可以上下左右四个方向行走，我们以二维数组中每一个数都作为起点和给定字符串做匹配，我们还需要一个和原数组等大小的 visited 数组，是 bool 型的，
// 用来记录当前位置是否已经被访问过，因为题目要求一个 cell 只能被访问一次。如果二维数组 board 的当前字符和目标字符串 word 对应的字符相等，则对其上下左右四个邻字符分别调用 DFS 的递归函数，
// 只要有一个返回 true，那么就表示可以找到对应的字符串，否则就不能找到

bool exist(vector<vector<char>> &board, string word)
{
	if (board.empty() || board[0].empty())
		return false;
	int m = board.size(), n = board[0].size();
	vector<vector<bool>> visited(m, vector<bool>(n, false));
	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (search(board, word, 0, i, j, visited))
				return true;
		}
	}
	return false;
}
bool search(vector<vector<char>> &board, string word, int idx, int i, int j, vector<vector<bool>> &visited)
{
	if (idx == word.size())
		return true;
	int m = board.size(), n = board[0].size();
	if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || board[i][j] != word[idx])
		return false;
	visited[i][j] = true;
	bool res = search(board, word, idx + 1, i - 1, j, visited) || search(board, word, idx + 1, i + 1, j, visited) || search(board, word, idx + 1, i, j - 1, visited) || search(board, word, idx + 1, i, j + 1, visited);
	visited[i][j] = false;
	return res;
}

// 36 largest rectangle in histogram (H)
// 这道题让求直方图中最大的矩形
// 一维 DP

//37
//https://siddontang.gitbooks.io/leetcode-solution/content/array/largest_rectangle_in_histogram.html

// 38 Binary tree inorder traverse (M)
// 二叉树的中序遍历顺序为左-根-右
void inorderTraversal(TreeNode *root, vector<int> res)
{
	if (root != NULL)
	{
		inorderTraversal(root->left, res);
		res.push_back(root->value);
		inorderTraversal(root->right, res);
	}
}

vector<int> Inorder(TreeNode *root)
{
	vector<int> res;
	inorderTraversal(root, res);
	return res;
}

//39 unique binary search tree (M)
// 卡塔兰数列的递推式为:
//可以得出Count的递推公式为,Count[i] = ∑ Count[0...k] * [k + 1....i]     0 <= k<i - 1,问题至此划归为一维动态规划。
int numTrees(int n)
{
	vector<int> count(n + 1, 0);
	count[0] = 1;
	count[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			count[i] += count[j] * count[i - j - 1];
		}
	}
	return count[n];
}

int numTrees(int n)
{
	vector<int> dp(n + 1);
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < i; j++)
			dp[i] += dp[j] * dp[i - j - 1];
	return dp[n];
}

//40 validate binary search tree (M)
// 验证二叉搜索树有很多种解法，可以利用它本身的性质来做，即左<根<右
// 解法1：递归判断数值的大小：左、右、根
//解法2：中序遍历，然后判断数值的递增
bool IsValidBST(TreeNode *root)
{
	vector<int> tmp = Inorder(root);
	for (vector<int>::iterator it = tmp.begin(); it < tmp.end() - 1; it++)
	{
		if (*it >= *(it + 1))
		{
			return false;
		}
	}
}

// 判断 BST 的合法性
bool isValidBST(TreeNode *root)
{
	return isValid(root, INT_MIN, INT_MAX);
}

bool isValid(TreeNode *root, int low, int high)
{
	if (root == NULL)
		return true;
	return root->val > low && root->val < high && isValid(root->left, low, root->val) && isValid(root->right, root->val, high);
}

//41 same tree (E)
bool Is_SameTree(TreeNode *p, TreeNode *q)
{
	if (p == NULL && q == NULL)
	{
		return true;
	}
	if ((p == NULL && q != NULL) || (p != NULL && q == NULL) || p->value != q->value)
	{
		return false;
	}
	// 左子树和左子数验证，右子树和右子数验证
	return Is_SameTree(p->left, p->left) && Is_SameTree(p->right, p->right);
}

//42 Symmetric tree(E)
bool IsSymmetric_recursive(TreeNode *left, TreeNode *right)
{
	if (left && right)
	{
		return true;
	}
	if ((left && !right) || (!left && right) || (left->value != right->value))
	{
		return false;
	}
	return IsSymmetric_recursive(left->left, right->right) && IsSymmetric_recursive(left->right, right->left);
}

bool IsSymmetric(TreeNode *root)
{
	if (root == NULL)
	{
		return true;
	}
	return IsSymmetric_recursive(root->left, root->right);
}

//43 Binary tree level order traverse (M)
// 层次遍历二叉数   // 使用queue
// 层序遍历二叉树是典型的广度优先搜索 BFS 的应用，但是这里稍微复杂一点的是，要把各个层的数分开，存到一个二维向量里面，大体思路还是基本相同的，
// 建立一个 queue，然后先把根节点放进去，这时候找根节点的左右两个子节点，这时候去掉根节点，此时 queue 里的元素就是下一层的所有节点，用一个 for 循环遍历它们，然后存到一个一维向量里，
// 遍历完之后再把这个一维向量存到二维向量里
void LevelTraverse(TreeNode *root)
{
	if (root == NULL)
	{
		return;
	}
	queue<TreeNode *> res;
	res.push(root);
	if (!res.empty())
	{
		TreeNode *tmp = res.front();
		cout << tmp->value;
		res.pop();
		if (root->left != NULL)
		{
			res.push(root->left);
		}
		if (root->right != NULL)
		{
			res.push(root->right);
		}
	}
}

//44 Maximum depth of binary Tree(E)
int maxDepth(TreeNode *root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + max((maxDepth(root->right)), maxDepth(root->left));
}

// 45 Construct binary tree from pre-order and in-order traverse (M)

//46 Best time to buy and sell stock (M)
// 这道题相当简单，感觉达不到Medium的难度，只需要遍历一次数组，用一个变量记录遍历过数中的最小值，然后每次计算当前值和这个最小值之间的差值最为利润，然后每次选较大的利润来更新。当遍历完成后当前利润即为所求
int maxProfit(vector<int> &prices)
{
	int res = 0;
	int buy = INT_MIN;
	for (int price : prices)
	{
		buy = min(buy, price);
		res = max(res, (price - buy));
	}
	return res;
}

// 47 Binary tree maximum path sum (H)
//在递归函数中，如果当前结点不存在，那么直接返回0。否则就分别对其左右子节点调用递归函数，由于路径和有可能为负数，
//而我们当然不希望加上负的路径和，所以我们和0相比，取较大的那个，就是要么不加，加就要加正数。然后我们来更新全局最大值结果res，
//就是以左子结点为终点的最大path之和加上以右子结点为终点的最大path之和，还要加上当前结点值，这样就组成了一个条完整的路径。
//而我们返回值是取left和right中的较大值加上当前结点值，因为我们返回值的定义是以当前结点为终点的path之和，
//所以只能取left和right中较大的那个值，而不是两个都要

int Max_PathSum_recursive(TreeNode *root, int res)
{
	if (root == NULL)
	{
		res = 0;
		return res;
	}
	int left = max(Max_PathSum_recursive(root->left, res), 0);
	int right = max(Max_PathSum_recursive(root->right, res), 0);
	res = max((left + right + root->value), res);
	return max(left, right) + root->value;
}

int Max_PathSum(TreeNode *root)
{
	int res = INT_MIN;
	Max_PathSum_recursive(root, res);
	return res;
}

//48 Longest Consecutive Sequence 求最长连续序列 (H)
//对数组中的每一个元素进行：在set中查找该value,然后删除value,去该数的前一个数pre=value-1,和后一个数behind=value+1;
//在数组中查找，然后res=behind-pre+1;再取每个res中的最大res;
int longestConsecutive(vector<int> &nums)
{
	int res = 0;
	unordered_set<int> tmp(nums.begin(), nums.end());
	for (int val : tmp)
	{
		if (!tmp.count(val))
		{
			continue;
		}
		tmp.erase(val);
		int pre = val - 1;
		int beh = val + 1;
		while (tmp.count(pre))
		{
			tmp.erase(pre);
			pre--;
		}
		while (tmp.count(beh))
		{
			tmp.erase(beh);
			beh++;
		}
		res = max(res, (beh - pre + 1));
	}
	return res;
}

//49 Single number (E)
//异或
class Solution_49
{
public:
	int singleNumber(vector<int> &nums)
	{
		int res = 0;
		for (auto num : nums)
			res ^= num;
		return res;
	}
};

// 50 Word break (M)
// 拆分词句问题是看给定的词句能分被拆分成字典里面的内容

// dp[i] 表示范围 [0, i) 内的子串是否可以拆分
// 注意这里 dp 数组的长度比s串的长度大1，是因为我们要 handle 空串的情况，我们初始化 dp[0] 为 true，然后开始遍历。注意这里我们需要两个 for 循环来遍历，因为此时已经没有递归函数了，
// 所以我们必须要遍历所有的子串，我们用j把 [0, i) 范围内的子串分为了两部分，[0, j) 和 [j, i)，其中范围 [0, j) 就是 dp[j]，范围 [j, i) 就是 s.substr(j, i-j)，其中 dp[j] 是之前的状态，
// 我们已经算出来了，可以直接取，只需要在字典中查找 s.substr(j, i-j) 是否存在了，如果二者均为 true，将 dp[i] 赋为 true，并且 break 掉，此时就不需要再用j去分 [0, i) 范围了，
// 因为 [0, i) 范围已经可以拆分了。最终我们返回 dp 数组的最后一个值，就是整个数组是否可以拆分的布尔值了
bool wordBreak(string s, vector<string> &wordDict)
{
	unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
	vector<bool> dp(s.size() + 1);
	dp[0] = true;
	for (int i = 0; i < dp.size(); ++i)
	{
		for (int j = 0; j < i; ++j)
		{
			if (dp[j] && wordSet.count(s.substr(j, i - j)))
			{
				dp[i] = true;
				break;
			}
		}
	}
	return dp.back();
}

//51 Linked list cycle (E)
//这道题就是判断一个链表是否存在环
bool hasCycle(ListNode *head)
{
	if (!head || !head->next)
	{
		return false;
	}
	ListNode *fast = head;
	ListNode *slow = head;
	while (fast->next != NULL && fast->next->next != NULL)
	{
		fast = fast->next->next;
		slow = slow->next;
		if (slow->value == fast->value)
		{
			return true;
		}
	}
}

// 52 Linked list cycle II (M)
// 这个求单链表中的环的起始点是之前那个判断单链表中是否有环的延伸，可参之前那道 Linked List Cycle。这里还是要设快慢指针，不过这次要记录两个指针相遇的位置，当两个指针相遇了后，
// 让其中一个指针从链表头开始，此时再相遇的位置就是链表中环的起始位置，为啥是这样呢，这里直接贴上热心网友「飞鸟想飞」的解释哈，因为快指针每次走2，慢指针每次走1，快指针走的距离是慢指针的两倍。
// 而快指针又比慢指针多走了一圈。所以 head 到环的起点+环的起点到他们相遇的点的距离 与 环一圈的距离相等。现在重新开始，head 运行到环起点 和 相遇点到环起点 的距离也是相等的，相当于他们同时减掉了 环的起点到他们相遇的点的距离
ListNode *detectCycle(ListNode *head)
{
	if (head && head->next)
	{
		return false;
	}
	ListNode *fast = head;
	ListNode *slow = head;
	while (fast->next != NULL && fast->next->next != NULL && slow->value != fast->value)
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	ListNode *tmp = head;
	while (tmp->value != fast->value)
	{
		tmp = tmp->next;
		fast = fast->next;
	}
	return tmp;
}

// 53 LRU cache (M)
// https://github.com/lucianzhong/fucking-algorithm/blob/master/%E9%AB%98%E9%A2%91%E9%9D%A2%E8%AF%95%E7%B3%BB%E5%88%97/LRU%E7%AE%97%E6%B3%95.md
// LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据
// LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体
// 到这里就能回答刚才“为什么必须要用双向链表”的问题了，因为我们需要删除操作。删除一个节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接查找前驱，保证操作的时间复杂度 $O(1)$
class Node
{
public
	int key, val;
public
	Node next, prev;
public
	Node(int k, int v)
	{
		this.key = k;
		this.val = v;
	}
}

class DoubleList
{
	// 在链表头部添加节点 x，时间 O(1)
public
	void addFirst(Node x);

	// 删除链表中的 x 节点（x 一定存在）
	// 由于是双链表且给的是目标 Node 节点，时间 O(1)
public
	void remove(Node x);

	// 删除链表中最后一个节点，并返回该节点，时间 O(1)
public
	Node removeLast();

	// 返回链表长度，时间 O(1)
public
	int size();
}

有了双向链表的实现，我们只需要在 LRU 算法中把它和哈希表结合起来即可。我们先把逻辑理清楚：

	// key 映射到 Node(key, val)
	HashMap<Integer, Node>
		map;
// Node(k1, v1) <-> Node(k2, v2)...
DoubleList cache;

int get(int key)
{
	if (key 不存在)
	{
		return -1;
	}
	else
	{
		将数据(key, val)
		提到开头； return val;
	}
}

void put(int key, int val)
{
	Node x = new Node(key, val);
	if (key 已存在)
	{
		把旧的数据删除；
		将新节点 x 插入到开头；
	}
	else
	{
		if (cache 已满)
		{
			删除链表的最后一个数据腾位置；
			删除 map 中映射到该数据的键；
		}
		将新节点 x 插入到开头；
			map 中新建 key 对新节点 x 的映射；
	}
}
如果能够看懂上述逻辑，翻译成代码就很容易理解了：

class LRUCache
{
	// key -> Node(key, val)
private
	HashMap<Integer, Node> map;
	// Node(k1, v1) <-> Node(k2, v2)...
private
	DoubleList cache;
	// 最大容量
private
	int cap;

public
	LRUCache(int capacity)
	{
		this.cap = capacity;
		map = new HashMap<>();
		cache = new DoubleList();
	}

public
	int get(int key)
	{
		if (!map.containsKey(key))
			return -1;
		int val = map.get(key).val;
		// 利用 put 方法把该数据提前
		put(key, val);
		return val;
	}

public
	void put(int key, int val)
	{
		// 先把新节点 x 做出来
		Node x = new Node(key, val);

		if (map.containsKey(key))
		{
			// 删除旧的节点，新的插到头部
			cache.remove(map.get(key));
			cache.addFirst(x);
			// 更新 map 中对应的数据
			map.put(key, x);
		}
		else
		{
			if (cap == cache.size())
			{
				// 删除链表最后一个数据
				Node last = cache.removeLast();
				map.remove(last.key);
			}
			// 直接添加到头部
			cache.addFirst(x);
			map.put(key, x);
		}
	}
}

//54 sort list(M)
//quick_sort
int
partition(vector<TreeNode *> num, int left, int right)
{
	int k = left;
	TreeNode *pivot = num[right];
	for (int i = left; i < right; i++)
	{
		if (num[i]->value < pivot->value)
		{
			swap(num[i]->value, num[k++]->value);
		}
	}
	swap(num[k]->value, num[right]->value);
	return k;
}

void Qucik_sort(vector<TreeNode *> num, int left, int right)
{
	while (left < right)
	{
		int pivot_index = partition(num, left, right);
		Qucik_sort(num, left, pivot_index - 1);
		Qucik_sort(num, pivot_index + 1, right);
	}
}

void quicksort(vector<int> &v, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int lower = left;
	int upper = right;
	while (lower < upper)
	{
		while (lower < upper && v[upper] >= v[lower])
		{			 //从后向前搜索
			upper--; // 找到第 1 个比基准数小的值，让它与基准值交换
		}
		swap(v[lower], v[upper]);
		while (lower < upper && v[lower] <= v[upper])
		{			 //从前向后搜索
			lower++; // 找到第 1 个比基准数大的值，让它与基准值交换
		}
		swap(v[lower], v[upper]);
		// 然后继续寻找，直到 i 与 j 相遇时结束，最后基准值所在的位置即 k 的位置，
		// 也就是说 k 左边的值均比 k 上的值小，而 k 右边的值都比 k 上的值大
	}
	quicksort(v, left, lower - 1);	//左段
	quicksort(v, upper + 1, right); //右段
}

//55 Maximum product subarray (M)
// 最大子数组乘积问题
//DP:两个数值，一个保存最大值，一个保存，最小值
// 其实这道题最直接的方法就是用 DP 来做，而且要用两个 dp 数组，其中 f[i] 表示子数组 [0, i] 范围内并且一定包含 nums[i] 数字的最大子数组乘积，
// g[i] 表示子数组 [0, i] 范围内并且一定包含 nums[i] 数字的最小子数组乘积，初始化时 f[0] 和 g[0] 都初始化为 nums[0]，
// 其余都初始化为0。那么从数组的第二个数字开始遍历，那么此时的最大值和最小值只会在这三个数字之间产生，
// 即 f[i-1]*nums[i]，g[i-1]*nums[i]，和 nums[i]。所以用三者中的最大值来更新 f[i]，用最小值来更新 g[i]，
// 然后用 f[i] 来更新结果 res 即可，由于最终的结果不一定会包括 nums[n-1] 这个数字，所以 f[n-1] 不一定是最终解，不断更新的结果 res 才是

// 当前的最大值等于已知的最大值、最小值和当前值的乘积，当前值，这三个数的最大值。
// 当前的最小值等于已知的最大值、最小值和当前值的乘积，当前值，这三个数的最小值。
// 结果是最大值数组中的最大值。
int maxProduct(vector<int> &nums)
{
	const int N = nums.size();
	vector<int> mx(N);
	vector<int> mn(N);
	int res = mx[0] = mn[0] = nums[0];
	for (int i = 1; i < N; ++i)
	{
		mx[i] = max(nums[i], max(mx[i - 1] * nums[i], mn[i - 1] * nums[i]));
		mn[i] = min(nums[i], min(mx[i - 1] * nums[i], mn[i - 1] * nums[i]));
		res = max(mx[i], res);
	}
	return res;
}

// 56 Min stack (E)
// 最小栈跟原来的栈相比就是多了一个功能，可以返回该栈的最小值
int Min_stack(stack<int> s)
{
	stack<int> s1;
	int res = s.top();
	while (!s.empty())
	{
		s.pop();
		if (res < s.top())
		{
			res = s.top();
		}
	}
	return res;
}

// 57  Intersection of two linked lists (M)
// 求两个链表的交点
int Get_length_of_list(ListNode *head)
{
	int length = 0;
	while (!head)
	{
		length++;
		head = head->next;
	}
	return length;
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
	int length_A = Get_length_of_list(headA);
	int length_B = Get_length_of_list(headB);

	if (length_A < length_B)
	{
		for (int i = 0; i < length_B - length_A; i++)
		{
			headB = headB->next;
		}
	}

	if (length_A > length_B)
	{
		for (int i = 0; i < length_A - length_B; i++)
		{
			headA = headA->next;
		}
	}

	while (headA && headB && headA != headB)
	{
		headA = headA->next;
		headB = headB->next;
	}
	return headA == headB ? headA : NULL;
}

// 58 Majority element (E)
// 哈希表  // unordered_map
int majorityElement(vector<int> &num)
{
	unordered_map<int, int> count;
	int res = 0;
	for (int i = 0; i < num.size(); i++)
	{
		count[num[i]]++;
	}
	for (unordered_map<int, int>::iterator iter = count.begin(); iter != count.end(); iter++)
	{
		if (iter->second > num.size() / 2)
		{
			res = iter->first;
		}
	}
	return res;
}

// 59 House robber (E)
int rob(vector<int> &num)
{
	vector<int> res = {num[0], max(num[0], num[1])};
	for (int i = 2; i < num.size(); i++)
	{
		res.push_back(max((num[i] + res[i - 2]), num[i]));
	}
	return res.back();
}

// 60 Number of islands (M)
// 这道求岛屿数量的题的本质是求矩阵中连续区域的个数，很容易想到需要用深度优先搜索 DFS 来解，我们需要建立一个 visited 数组用来记录某个位置是否被访问过，对于一个为 ‘1’ 且未被访问过的位置，
// 递归进入其上下左右位置上为 ‘1’ 的数，将其 visited 对应值赋为 true，继续进入其所有相连的邻位置，这样可以将这个连通区域所有的数找出来，并将其对应的 visited 中的值赋 true，找完相邻区域后，
// 将结果 res 自增1，然后再继续找下一个为 ‘1’ 且未被访问过的位置，以此类推直至遍历完整个原数组即可得到最终结果

void Number_of_Islands_DFS(vector<vector<char>> &grid, vector<vector<bool>> visited, int x, int y)
{
	if (x < 0 || x >= grid.size())
		return;
	if (y < 0 || y >= grid[0].size())
		return;
	if (grid[x][y] != '1' || visited[x][y])
		return;
	visited[x][y] = true;
	Number_of_Islands_DFS(grid, visited, x - 1, y);
	Number_of_Islands_DFS(grid, visited, x + 1, y);
	Number_of_Islands_DFS(grid, visited, x, y - 1);
	Number_of_Islands_DFS(grid, visited, x, y + 1);
}

int Number_of_Islands(vector<vector<char>> &grid)
{
	int res = 0;
	int row = grid.size();
	int colume = grid[0].size();
	vector<vector<bool>> visited(row, vector<bool>(colume, false));
	for (int i = 0; i < row; i++)
	{
		for (int j = 0; j < colume; j++)
		{
			if (!visited[i][j] && grid[i][j] == '1')
			{
				Number_of_Islands_DFS(grid, visited, i, j);
				res++;
			}
		}
	}
	return res;
}

// 61 Reverse linked list (E)
// 使用stack 或者 使用循环
ListNode *reverseList(ListNode *head)
{
	stack<ListNode *> st;
	ListNode *res = NULL;
	while (head)
	{
		st.push(head);
		head = head->next;
	}

	res = st.top();
	while (!st.empty())
	{
		st.pop();
		res->next = st.top();
	}
	return res;
}

// 62 course schedule (M)
//这个问题等价于判定一个有向图中是否存在环。如果存在环，就不存在拓扑序，也就是不可能上完所有的课程
//Topological Sort via DFS 拓扑排序可以用深度优先搜索来实现。
// Topological sort could also be done via BFS 拓扑排序可以用广度优先搜索来实现。
//http://www.cnblogs.com/grandyang/p/4484571.html

// 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习
// 这个问题实际上是判断有向图是否有环，可以通过拓扑排序来处理

// 下面来看 DFS 的解法，也需要建立有向图，还是用二维数组来建立，和 BFS 不同的是，像现在需要一个一维数组 visit 来记录访问状态，这里有三种状态，0表示还未访问过，1表示已经访问了，-1 表示有冲突。
// 大体思路是，先建立好有向图，然后从第一个门课开始，找其可构成哪门课，暂时将当前课程标记为已访问，然后对新得到的课程调用 DFS 递归，直到出现新的课程已经访问过了，
// 则返回 false，没有冲突的话返回 true，然后把标记为已访问的课程改为未访问

// BFS




bool canFinishDFS(vector<vector<int>> &graph, vector<int> &visit, int i)
{
	if (visit[i] == -1)
		return false;
	if (visit[i] == 1)
		return true;
	// visit[i]==0;
	for (auto a : graph[i])
	{
		if (!canFinishDFS(graph, visit, a))
			return false;
	}
	visit[i] = 1;
	return true;
}

// 63 Implement trie(Prefix tree)  (M)
// 实现字典树(前缀树)
// http://www.cnblogs.com/grandyang/p/4491665.html

//64 Kth largest element in an array (M)
int findKthLargest(vector<int> &nums, int k)
{
	sort(nums.begin(), nums.end());
	return *(nums.begin() + k);
}

// 65 Maximal square(M)
// 最大正方形
// 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积
// 示例:
// 输入:
// 1 0 1 0 0
// 1 0 1 1 1
// 1 1 1 1 1
// 1 0 0 1 0
// 输出: 4

// 做法是使用 DP，建立一个二维 dp 数组，其中 dp[i][j] 表示到达 (i, j) 位置所能组成的最大正方形的边长。
// 我们首先来考虑边界情况，也就是当i或j为0的情况，那么在首行或者首列中，必定有一个方向长度为1，
// 那么就无法组成长度超过1的正方形，最多能组成长度为1的正方形，条件是当前位置为1。边界条件处理完了，
// 再来看一般情况的递推公式怎么办，对于任意一点 dp[i][j]，由于该点是正方形的右下角，
// 所以该点的右边，下边，右下边都不用考虑，关心的就是左边，上边，和左上边。这三个位置的dp值 suppose 都应该算好的，
// 还有就是要知道一点，只有当前 (i, j) 位置为1，dp[i][j] 才有可能大于0，
// 否则 dp[i][j] 一定为0。当 (i, j) 位置为1，此时要看 dp[i-1][j-1], dp[i][j-1]，和 dp[i-1][j] 这三个位置，
// 我们找其中最小的值，并加上1，就是 dp[i][j] 的当前值了，
// 做法是使用 DP，建立一个二维 dp 数组，其中 dp[i][j] 表示到达 (i, j) 位置所能组成的最大正方形的边长。我们首先来考虑边界情况，也就是当i或j为0的情况，那么在首行或者首列中，必定有一个方向长度为1，
// 那么就无法组成长度超过1的正方形，最多能组成长度为1的正方形，条件是当前位置为1。边界条件处理完了，再来看一般情况的递推公式怎么办，对于任意一点 dp[i][j]，由于该点是正方形的右下角，
// 所以该点的右边，下边，右下边都不用考虑，关心的就是左边，上边，和左上边。这三个位置的dp值 suppose 都应该算好的，还有就是要知道一点，只有当前 (i, j) 位置为1，dp[i][j] 才有可能大于0，
// 否则 dp[i][j] 一定为0。当 (i, j) 位置为1，此时要看 dp[i-1][j-1], dp[i][j-1]，和 dp[i-1][j] 这三个位置，我们找其中最小的值，并加上1，就是 dp[i][j] 的当前值了，
// 这个并不难想，毕竟不能有0存在，所以只能取交集，最后再用 dp[i][j] 的值来更新结果 res 的值即可
int maximalSquare(vector<vector<char>> &matrix)
{
	if (matrix.empty() || matrix[0].empty())
		return 0;
	int m = matrix.size(), n = matrix[0].size(), res = 0;
	vector<vector<int>> dp(m, vector<int>(n, 0));
	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (i == 0 || j == 0)
				dp[i][j] = matrix[i][j] - '0';
			else if (matrix[i][j] == '1')
			{
				dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
			}
			res = max(res, dp[i][j]);
		}
	}
	return res * res;
}

//66 Invert binary tree (E)
TreeNode *invertTree(TreeNode *root)
{
	if (root == NULL)
	{
		return NULL;
	}
	swap(root->left, root->right);
	invertTree(root->left);
	invertTree(root->right);
}

//67 Palindrome linked list (E)
//回文链表  // 判断一个链表是否为回文链表
bool isPalindrome(ListNode *head)
{
	ListNode *slow = head;
	ListNode *fast = head;
	stack<int> front_half;
	while (fast && fast->next->next)
	{
		slow = slow->next;
		fast = fast->next->next;
		front_half.push(slow->value);
	}
	while (slow)
	{
		slow = slow->next;
		int tmp = front_half.top();
		front_half.pop();
		if (slow->value != tmp)
		{
			return false;
		}
	}
	return true;
}

// 68 Lowest common ancestor of binary tree (M)
//二叉树的最小共同父节点
// 由于这道题限制了p和q一定都在二叉树中存在，那么如果当前结点不等于p或q，p和q要么分别位于左右子树中，要么同时位于左子树，或者同时位于右子树，那么我们分别来讨论：
// - 若p和q分别位于左右子树中，那么对左右子结点调用递归函数，会分别返回p和q结点的位置，而当前结点正好就是p和q的最小共同父结点，直接返回当前结点即可，这就是题目中的例子1的情况。
// - 若p和q同时位于左子树，这里有两种情况，一种情况是 left 会返回p和q中较高的那个位置，而 right 会返回空，所以最终返回非空的 left 即可，这就是题目中的例子2的情况。
// 还有一种情况是会返回p和q的最小父结点，就是说当前结点的左子树中的某个结点才是p和q的最小父结点，会被返回。
// - 若p和q同时位于右子树，同样这里有两种情况，一种情况是 right 会返回p和q中较高的那个位置，而 left 会返回空，所以最终返回非空的 right 即可，还有一种情况是会返回p和q的最小父结点，
// 就是说当前结点的右子树中的某个结点才是p和q的最小父结点，会被返回，

TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
{
	if (!root || p == root || q == root)
	{
		return root;
	}
	TreeNode *left = lowestCommonAncestor(root->left, p, q);
	TreeNode *right = lowestCommonAncestor(root->right, p, q);
	if (left && right)
	{
		return root;
	}
	return left ? left : right;
}

// 69 Product of array except self (M)
// 前面所有数乘以后面所有数
// 这道题给定我们一个数组，让我们返回一个新数组，对于每一个位置上的数是其他位置上数的乘积，并且限定了时间复杂度 O(n)，并且不让我们用除法。如果让用除法的话，那这道题就应该属于 Easy，因为可以先遍历一遍数组求出所有数字之积，
// 然后除以对应位置的上的数字。但是这道题禁止我们使用除法，那么我们只能另辟蹊径。我们想，对于某一个数字，如果我们知道其前面所有数字的乘积，同时也知道后面所有的数乘积，那么二者相乘就是我们要的结果，
// 所以我们只要分别创建出这两个数组即可，分别从数组的两个方向遍历就可以分别创建出乘积累积数组
vector<int> productExceptSelf(vector<int> &nums)
{
	int n = nums.size();
	vector<int> res(n, 1);
	vector<int> behind(n, 1);
	vector<int> forward(n, 1);
	for (int i = 0; i < n - 1; i++)
	{
		forward[i + 1] = forward[i] * nums[i];
	}
	for (int i = n - 1; i > 0; --i)
	{
		behind[i - 1] = behind[i] * nums[i];
	}
	for (int i = 0; i < n; ++i)
	{
		res[i] = forward[i] * behind[i];
	}
	return res;
}

// 70 Sliding window maximum (H)
// 这道题给定了一个数组，还给了一个窗口大小k，让我们每次向右滑动一个数字，每次返回窗口内的数字的最大值
vector<int> maxSlidingWindow(vector<int> &nums, int k)
{
	vector<int> res;
	priority_queue<pair<int, int>> q; // 最大堆   // 优先队列是大顶堆，队头元素最大
	for (int i = 0; i < nums.size(); ++i)
	{
		while (!q.empty() && q.top().second <= i - k)
			q.pop();
		q.push({nums[i], i});
		if (i >= k - 1)
			res.push_back(q.top().first);
	}
	return res;
}

// 71 Search a 2D matrix II (M)
// 那么我们就可以和目标数相比较，如果目标数大，就往右搜，如果目标数小，就往上搜。这样就可以判断目标数是否存在。当然我们也可以把起始数放在右上角，往左和下搜，停止条件设置正确就行
bool searchMatrix(vector<vector<int>> &matrix, int target)
{
	int colume = matrix.size();
	int row = matrix[0].size();
	int y = 0;
	int x = colume;
	if (matrix[colume][y] > target)
	{
		colume--;
	}
	else if (matrix[colume][y] < target)
	{
		y++;
	}
	else
	{
		return true;
	}
	if (x < 0 || y >= matrix[0].size())
	{
		return false;
	}
}

// 72 Meeting rooms II (M)
// 这道题是之前那道 Meeting Rooms 的拓展，那道题只问我们是否能参加所有的会，也就是看会议之间有没有时间冲突，而这道题让求最少需要安排几个会议室，有时间冲突的肯定需要安排在不同的会议室。
// 这道题有好几种解法，先来看使用 TreeMap 来做的，遍历时间区间，对于起始时间，映射值自增1，对于结束时间，映射值自减1，然后定义结果变量 res，和房间数 rooms，遍历 TreeMap，时间从小到大，
// 房间数每次加上映射值，然后更新结果 res，遇到起始时间，映射是正数，则房间数会增加，如果一个时间是一个会议的结束时间，也是另一个会议的开始时间，则映射值先减后加仍为0，并不用分配新的房间，
// 而结束时间的映射值为负数更不会增加房间数
struct intervals
{
	int start;
	int end;
};

int minMeetingRooms(vector<Interval> &intervals)
{
	vector<int> starts;
	vector<int> ends;
	for (auto x : intervals)
	{
		starts.push_back(x.start);
		ends.push_back(x.end);
	}
	sort(starts.begin(), starts.end());
	sort(ends.begin(), ends.end());

	int end_index = 0;
	int res = 0;
	for (int i = 0; i < starts.size(); i++)
	{
		if (starts[i] < ends[end_index])
		{
			res++;
		}
		else
		{
			end_index++;
		}
	}
	return res;
}

// 73 Perfect squares (M)
// 这道题说是给我们一个正整数，求它最少能由几个完全平方数组成。这道题是考察四平方和定理
int numSquares(int n)
{
	vector<int> dp(n + 1, INT_MAX);
	dp[0] = 0;
	for (int a = 0; a <= n; a++)
	{
		for (int b = 0; a + b * b <= n; b++)
		{
			dp[a + b * b] = min(dp[a + b * b], dp[a] + 1);
		}
	}
	return dp.back();
}

// 74 Move zeroes (M)
// For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0]

void moveZeroes(vector<int> &nums)
{
	for (int i = 0, j = nums.size() - 1; i < nums.size(); i++)
	{
		if (nums[i] == 0)
		{
			swap(nums[i], nums[j--]);
		}
	}
}

// 75 Find the Duplicate Number 寻找重复数(M)
// 二分搜索
int findDuplicate(vector<int> &nums)
{
	int left = 0;
	int right = nums.size() - 1;
	int cnt = 0;
	while (left < right)
	{
		int mid = left + (right - left) * 0.5;
		for (auto a : nums)
		{
			if (a <= mid)
			{
				cnt++;
			}
		}

		if (cnt > mid)
		{
			right = mid;
		}
		else
		{
			left = mid + 1;
		}
	}
	return left;
}

// 76 Seriallize and deserialize binary tree (H)
// 二叉树的序列化和去序列化
// http://www.cnblogs.com/grandyang/p/4913869.html
class Codec
{
public:
	// Encodes a tree to a single string.
	string serialize(TreeNode *root)
	{
		ostringstream out;
		serialize(root, out);
		return out.str();
	}
	// Decodes your encoded data to tree.
	TreeNode *deserialize(string data)
	{
		istringstream in(data);
		return deserialize(in);
	}

private:
	void serialize(TreeNode *root, ostringstream &out)
	{
		if (root)
		{
			out << root->val << ' ';
			serialize(root->left, out);
			serialize(root->right, out);
		}
		else
		{
			out << "# ";
		}
	}

	// 递归调用
	TreeNode *deserialize(istringstream &in)
	{
		string val;
		in >> val;
		if (val == "#")
			return nullptr;
		TreeNode *root = new TreeNode(stoi(val));
		root->left = deserialize(in);
		root->right = deserialize(in);
		return root;
	}
};

// 77 Longest increasing subsequence (M)
// 一维的DP

int lengthOfLIS(vector<int> &nums)
{
	vector<int> dp(nums.size(), 1);
	int res = 0;
	for (int i = 0; i < nums.size(); ++i)
	{
		for (int j = 0; j < i; ++j)
		{
			if (nums[i] > nums[j])
			{
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		res = max(res, dp[i]);
	}
	return res;
}

// 78 Remove invalid parentheses (H)







// 79  Best time to buy and sell stock with cooldown (M)
// 股票






// 80 Burst balloons (M)
// 这道题提出了一种打气球的游戏，每个气球都对应着一个数字，每次打爆一个气球，得到的金币数是被打爆的气球的数字和其两边的气球上的数字相乘，如果旁边没有气球了，则按1算，以此类推，求能得到的最多金币数
// 那么对于有很多数的区间 [i, j]，如何来更新呢？现在是想知道 dp[i][j] 的值，这个区间可能比较大，但是如果知道了所有的小区间的 dp 值，然后聚沙成塔，逐步的就能推出大区间的 dp 值了。还是要遍历这个区间内的每个气球，就用k来遍历吧，k在区间 [i, j] 中，假如第k个气球最后被打爆，那么此时区间 [i, j] 被分成了三部分，[i, k-1]，[k]，和 [k+1, j]，只要之前更新过了 [i, k-1] 和 [k+1, j] 这两个子区间的 dp 值，可以直接用 dp[i][k-1] 和 dp[k+1][j]，那么最后被打爆的第k个气球的得分该怎么算呢，你可能会下意识的说，就乘以周围两个气球被 nums[k-1] * nums[k] * nums[k+1]，但其实这样是错误的，为啥呢？dp[i][k-1] 的意义是什么呢，是打爆区间 [i, k-1] 内所有的气球后的最大得分，此时第 k-1 个气球已经不能用了，同理，第 k+1 个气球也不能用了，相当于区间 [i, j] 中除了第k个气球，其他的已经爆了，那么周围的气球只能是第 i-1 个，和第 j+1 个了，所以得分应为 nums[i-1] * nums[k] * nums[j+1]，分析到这里，状态转移方程应该已经跃然纸上了吧，如下所示：
// dp[i][j] = max(dp[i][j], nums[i - 1] * nums[k] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j])                 ( i ≤ k ≤ j )
int maxCoins(vector<int> &nums)
{
	int n = nums.size();
	nums.insert(nums.begin(), 1);
	nums.push_back(1);
	vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
	for (int len = 1; len <= n; ++len)
	{
		for (int i = 1; i <= n - len + 1; ++i)
		{
			int j = i + len - 1;
			for (int k = i; k <= j; ++k)
			{
				dp[i][j] = max(dp[i][j], nums[i - 1] * nums[k] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j]);
			}
		}
	}
	return dp[1][n];
}

// 81 Coin change (M)
// 先看下题目：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1
// https://github.com/lucianzhong/fucking-algorithm/blob/master/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E8%AF%A6%E8%A7%A3%E8%BF%9B%E9%98%B6.md
int coinChange(vector<int> &coins, int amount)
{
	// dp[i] = x 表示，当目标金额为 i 时，至少需要 x 枚硬币
	vector<int> DP(amount + 1, amount + 1); // 数组大小为amount+1,初始值也为amount+1
	DP[0] = 0;
	for (int i = 0; i < amount + 1; i++)
	{
		for (coin : coins)
		{
			if ((i - coin) < 0)
			{
				continue;
			}

			DP[i] = min(DP[i], DP[i - coin] + 1);
		}
	}
	return DP[amount];
}

// 82 House robber II (M)
// 这道题是之前那道 House Robber 的拓展，现在房子排成了一个圆圈，则如果抢了第一家，就不能抢最后一家，因为首尾相连了，所以第一家和最后一家只能抢其中的一家，或者都不抢，
// 那这里变通一下，如果把第一家和最后一家分别去掉，各算一遍能抢的最大值，然后比较两个值取其中较大的一个即为所求。那只需参考之前的 House Robber 中的解题方法，然后调用两边取较大值
int rob(vector<int> &nums)
{
	if (nums.size() <= 1)
		return nums.empty() ? 0 : nums[0];
	return max(rob(nums, 0, nums.size() - 1), rob(nums, 1, nums.size()));
}
int rob(vector<int> &nums, int left, int right)
{
	if (right - left <= 1)
		return nums[left];
	vector<int> dp(right, 0);
	dp[left] = nums[left];
	dp[left + 1] = max(nums[left], nums[left + 1]);
	for (int i = left + 2; i < right; ++i)
	{
		dp[i] = max(nums[i] + dp[i - 2], dp[i - 1]);
	}
	return dp.back();
}

// 83 Counting bits (M)
// 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示
// bitset()
int Bits(int n)
{
	int res = 0;
	while (n)
	{
		if (n & 1 == 1)
		{
			res++;
		}
		n >>= 1;
	}
	return res;
}

// 84 Top k frequent elements (M)
// 这道题给了我们一个数组，让统计前k个高频的数字，可以用堆排序来做，使用一个最大堆来按照映射次数从大到小排列，在 C++ 中使用 priority_queue 来实现，默认是最大堆

vector<int> topKFrequent(vector<int> &nums, int k)
{
	unordered_map<int, int> m;
	priority_queue<pair<int, int>> q;
	vector<int> res;
	for (auto a : nums)
		++m[a];
	for (auto it : m)
		q.push({it.second, it.first});
	for (int i = 0; i < k; ++i)
	{
		res.push_back(q.top().second);
		q.pop();
	}
	return res;
}

// 85 Decode string (M)
// 当然需要用 stack 来辅助运算，我们用两个 stack，一个用来保存个数，一个用来保存字符串，我们遍历输入字符串，如果遇到数字，我们更新计数变量 cnt；如果遇到左括号，我们把当前 cnt 压入数字栈中，把当前t压入字符串栈中
// 如果遇到右括号时，我们取出数字栈中顶元素，存入变量k，然后给字符串栈的顶元素循环加上k个t字符串，然后取出顶元素存入字符串t中；如果遇到字母，我们直接加入字符串t中即可
string decodeString(string s)
{
	string t = "";
	stack<int> s_num;
	stack<string> s_str;
	int cnt = 0;
	for (int i = 0; i < s.size(); ++i)
	{
		if (s[i] >= '0' && s[i] <= '9')
		{
			cnt = 10 * cnt + s[i] - '0';
		}
		else if (s[i] == '[')
		{
			s_num.push(cnt);
			s_str.push(t);
			cnt = 0;
			t.clear();
		}
		else if (s[i] == ']')
		{
			int k = s_num.top();
			s_num.pop();
			for (int j = 0; j < k; ++j)
				s_str.top() += t;
			t = s_str.top();
			s_str.pop();
		}
		else
		{
			t += s[i];
		}
	}
	return s_str.empty() ? t : s_str.top();
}

// 86 Queue reconstruction by height (M)

// 87 Partition equal subset sum (M)
// 这道题给了我们一个数组，问这个数组能不能分成两个非空子集合，使得两个子集合的元素之和相同
// 原数组所有数字和一定是偶数，不然根本无法拆成两个和相同的子集合，只需要算出原数组的数字之和，然后除以2，就是 target，
// 那么问题就转换为能不能找到一个非空子集合，使得其数字之和为 target
// 定义一个一维的 dp 数组，其中 dp[i] 表示原数组是否可以取出若干个数字，其和为i。那么最后只需要返回 dp[target] 就行了
// 第二个 for 循环一定要从 target 遍历到 nums[i]，而不能反过来，想想为什么呢？因为如果从 nums[i] 遍历到 target 的话，假如 nums[i]=1 的话，那么 [1, target] 中所有的 dp 值都是 true，
// 因为 dp[0] 是 true，dp[1] 会或上 dp[0]，为 true，dp[2] 会或上 dp[1]，为 true，依此类推，完全使的 dp 数组失效了

bool canPartition(vector<int> &nums)
{
	int sum = accumulate(nums.begin(), nums.end(), 0);
	int target = sum / 2;
	if (sum & 1)
		return false;
	vector<bool> dp(target + 1, false);
	dp[0] = true;
	for (int num : nums)
	{
		for (int i = target; i >= num; --i)
		{
			dp[i] = dp[i] || dp[i - num];
		}
	}
	return dp[target];
}

// 88 Path sum III (E)
// 给一课二叉树，和一个目标值，节点上的值有正有负，返回树中和等于目标值的路径条数，让你编写 pathSum 函数：
/* 有了以上铺垫，详细注释一下代码 */
int pathSum(TreeNode root, int sum)
{
	if (root == null)
		return 0;
	int pathImLeading = count(root, sum);		 // 自己为开头的路径数
	int leftPathSum = pathSum(root.left, sum);	 // 左边路径总数（相信他能算出来）
	int rightPathSum = pathSum(root.right, sum); // 右边路径总数（相信他能算出来）
	return leftPathSum + rightPathSum + pathImLeading;
}
int count(TreeNode node, int sum)
{
	if (node == null)
		return 0;
	// 我自己能不能独当一面，作为一条单独的路径呢？
	int isMe = (node.val == sum) ? 1 : 0;
	// 左边的小老弟，你那边能凑几个 sum - node.val 呀？
	int leftBrother = count(node.left, sum - node.val);
	// 右边的小老弟，你那边能凑几个 sum - node.val 呀？
	int rightBrother = count(node.right, sum - node.val);
	return isMe + leftBrother + rightBrother; // 我这能凑这么多个
}

// 89 Find all anagrams in a string (E)
// 这道题给了我们两个字符串s和p，让在s中找字符串p的所有变位次的位置，所谓变位次就是字符种类个数均相同但是顺序可以不同的两个词
// 滑动窗口法

List<Integer> findAnagrams(String s, String p)
{
	ArrayList<Integer> result = new ArrayList<>();
	if (s == null || p == null)
		return result;
	int left = 0, right = 0, count = p.length();
	int[] map = new int[256];
	char[] sc = s.toCharArray();
	for (char c : p.toCharArray())
		map[c]++;
	while (right < s.length())
	{
		if (map[sc[right++]]-- >= 1)
			count--;
		if (count == 0)
			result.add(left);
		if (right - left == p.length() && map[sc[left++]]++ >= 0)
			count++;
	}
	return result;
}

// 90 Find all numbers disappeared in an array (E)
// 这道题让我们找出数组中所有消失的数
// 已经告诉我们缺少了部分数字，那么我们可以先用set进行去重。然后再次遍历1~N各个数字，然后找出没有在set中出现的数字即可

// 首先来看第一种解法，这种解法的思路路是，对于每个数字nums[i]，如果其对应的nums[nums[i] - 1]是正数，我们就赋值为其相反数，如果已经是负数了，就不变了，那么最后我们只要把留下的整数对应的位置加入结果res中即可
class Solution
{
public:
	vector<int> findDisappearedNumbers(vector<int> &nums)
	{
		vector<int> res;
		for (int i = 0; i < nums.size(); ++i)
		{
			int idx = abs(nums[i]) - 1;
			nums[idx] = (nums[idx] > 0) ? -nums[idx] : nums[idx];
		}
		for (int i = 0; i < nums.size(); ++i)
		{
			if (nums[i] > 0)
			{
				res.push_back(i + 1);
			}
		}
		return res;
	}
};

// 91 Hamming distance (E)
// 这道题让我求两个数字之间的汉明距离，题目中解释的很清楚了，两个数字之间的汉明距离就是其二进制数对应位不同的个数，
// 那么最直接了当的做法就是按位分别取出两个数对应位上的数并异或，
// 我们知道异或的性质上相同的为0，不同的为1，我们只要把为1的情况累加起来就是汉明距离了
int hammingDistance(int x, int y)
{
	int res = 0;
	int exc = x ^ y;
	while (exc)
	{
		++res;
		exc &= (exc - 1);
	}
	return res;
}

// 92 Target sum (M)
// 这道题给了我们一个数组，和一个目标值，让给数组中每个数字加上正号或负号，然后求和要和目标值相等，求有多少中不同的情况
// 那么对于这种求多种情况的问题，博主最想到的方法使用递归来做。从第一个数字，调用递归函数，在递归函数中，
// 分别对目标值进行加上当前数字调用递归，和减去当前数字调用递归，
// 这样会涵盖所有情况，并且当所有数字遍历完成后，若目标值为0了，则结果 res 自增1

class Solution
{
public:
	int findTargetSumWays(vector<int> &nums, int S)
	{
		int res = 0;
		helper(nums, S, 0, res);
		return res;
	}
	void helper(vector<int> &nums, long S, int start, int &res)
	{
		if (start >= nums.size())
		{
			if (S == 0)
				++res;
			return;
		}
		helper(nums, S - nums[start], start + 1, res);
		helper(nums, S + nums[start], start + 1, res);
	}
};

// 93 Convert BST to greater tree (E)
// 题目的意思是给出一个二分查找树，更改里面的节点值，使得更改后的节点值为原来的节点加上所有比它大的节点的值。比如例子中的节点5，因为只有节点13比它大，所以更改的值为5+13=18，而对于节点2，因为节点5和节点13都比它大，所以更改的值为2+5+13=20。

// 题目看起来似乎蛮复杂的，最笨的方法就是对于某一个节点得找出所有比它大的节点，然后把值相加。但是这其中有很多重复的工作，同时也没有利用好题目给出的是二分查找树这一条件。

// 二分查找树的特点是中序遍历的结果是一个升序序列。而我们做加法时最简单的顺序就是从最大的值开始，降序地做下去。在树中对应的就是最右的叶子节点开始，因为该节点是最大的。如果对二分查找树有一定的敏感度的话，应该很容易就发现一个性质：如果我们按照中序遍历的逆序，即先右子节点，再父节点，最后左子节点顺序遍历的话，刚好就能降序地访问每一个节点。比如例子中就会是以13，5，2的顺序访问，这样我们每访问一个节点，就记录下到该节点的和，并在访问下一节点时将该和值加到节点的值上。以例子说明：
// 初始sum为0。
// 访问到13，更新节点值为13+sum=13+0=13，sum更新为sum+13=0+13=13；
// 访问到5，更新节点值为5+sum=5+13=18，sum更新为sum+5=13+5=18;
// 访问到2，更新节点值为2+sum=2+18=20，sum更新为sum+2=18+2=20;

// 因此，题目其实考的就是BST中序对应的逆序遍历，先访问右子树，然后父节点，最后左子树，并在访问过程中记录已访问的节点总和，
//  累加到当前的节点上。见下面我的代码

class Solution
{
public:
	void dfs(TreeNode *root, int &sum)
	{
		if (root->right)
			dfs(root->right, sum);

		int temp = root->val;
		root->val += sum;
		sum += temp;

		if (root->left)
			dfs(root->left, sum);
	}

	TreeNode *convertBST(TreeNode *root)
	{
		if (root)
		{
			int sum = 0;
			dfs(root, sum);
		}

		return root;
	}
};

// 94 Diameter of binary tree (E)
// 这道题让我们求二叉树的直径，并告诉了我们直径就是两点之间的最远距离，根据题目中的例子也不难理解题意。
// 我们再来仔细观察例子中的那两个最长路径[4,2,1,3] 和 [5,2,1,3]，我们转换一种角度来看，是不是其实就是根结点1的左右两个子树的深度之和呢。
// 那么我们只要对每一个结点求出其左右子树深度之和，这个值作为一个候选值，然后再对左右子结点分别调用求直径对递归函数，这三个值相互比较，
// 取最大的值更新结果res，因为直径不一定会经过根结点，所以才要对左右子结点再分别算一次

int diameterOfBinaryTree(TreeNode *root)
{
	int res = 0;
	maxDepth(root, res);
	return res;
}
int maxDepth(TreeNode *node, int &res)
{
	if (!node)
		return 0;
	int left = maxDepth(node->left, res);
	int right = maxDepth(node->right, res);
	res = max(res, left + right);
	return max(left, right) + 1;
}

// 95 Subarray sum equals to k (M)
// 道题给了我们一个数组，让我们求和为k的连续子数组的个数
// 先排序在使用双指针
int subarraySum(vector<int>& nums, int k) {
        int res = 0, n = nums.size();
        for (int i = 0; i < n; ++i) {
            int sum = nums[i];
            if (sum == k) ++res;
            for (int j = i + 1; j < n; ++j) {
                sum += nums[j];
                if (sum == k) ++res;
            }
        }
        return res;
    }


// 96 subtree of another tree (E)
bool isSubtree(TreeNode *s, TreeNode *t)
{
	if (!s)
		return false;
	if (isSame(s, t))
		return true;
	return isSubtree(s->left, t) || isSubtree(s->right, t);
}
bool isSame(TreeNode *s, TreeNode *t)
{
	if (!s && !t)
		return true;
	if (!s || !t)
		return false;
	if (s->val != t->val)
		return false;
	return isSame(s->left, t->left) && isSame(s->right, t->right);
}

// 97 shortest unsorted continous subarray (E)




// 98 Merge two binary trees (E)
// Merge Two Binary Trees 合并二叉树
// 这道题给了两个二叉树，让我们合并成一个，规则是，都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。那么根据过往经验，
// 处理二叉树问题的神器就是递归。
// 根据题目中的规则，如果要处理的相同位置上的两个结点都不存在的话，直接返回即可，如果 t1 存在，t2 不存在，就以 t1 的结点值建立一个新结点，
// 然后分别对 t1 的左右子结点和空结点调用递归函数，
// 反之，如果 t1 不存在，t2 存在，就以 t2 的结点值建立一个新结点，然后分别对 t2 的左右子结点和空结点调用递归函数。
// 如果 t1 和 t2 都存在，就以 t1 和 t2 的结点值之和建立一个新结点，然后分别对 t1 的左右子结点和 t2 的左右子结点调用递归函数

TreeNode *mergeTrees(TreeNode *t1, TreeNode *t2)
{
	if (!t1)
		return t2;
	if (!t2)
		return t1;
	TreeNode *t = new TreeNode(t1->val + t2->val);
	t->left = mergeTrees(t1->left, t2->left);
	t->right = mergeTrees(t1->right, t2->right);
	return t;
}

// 99 Task scheduler (M)
// 任务行程表
// Example 1:
// Input: tasks = ['A','A','A','B','B','B'], n = 2
// Output: 8
// Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
// Note:
// The number of tasks is in the range [1, 10000].
// The integer n is in the range [0, 100].
// 这道题让我们安排CPU的任务，规定在两个相同任务之间至少隔n个时间点

// 先找出出现次数最多的字符ch（如果有多个最多的字符，把初始位置扩大即可），按照间隔求出最远的位置，而出现次数小ch的字符完全可以填充在其间隔之间，如果间隔的数目不足，
// 可以把某个间隔扩大（如果间隔不足，总长度其实就是原来的数组的个数）

bool cmp(int a, int b)
{
	return a > b;
}

int leastInterval(vector<char> &tasks, int n)
{
	int m = tasks.size();
	int arr[30];
	memset(arr, 0, sizeof(arr));
	for (int i = 0; i < m; i++)
		arr[tasks[i] - 65]++;
	sort(arr, arr + 30, cmp);
	int sum = 1;
	for (int i = 1; i < 30; i++)
		if (arr[i] == arr[i - 1])
			sum++;
		else
			break;
	//int k = max(n+1,sum);
	int k = n + 1;
	int ans = sum + (arr[0] - 1) * k;
	ans = max(ans, m);
	return ans;
}

// 100 Palindromic substrings (M)
// 算有多少个回文子字符串  // 子串用双指针的方法

int count_sub_strings(string s)
{
	if (s.empty())
	{
		return 0;
	}
	int res = 0;
	for (int i = 0; i < s.size(); i++)
	{
		helper(s, i, i, res); // 分奇数和偶数的情况讨论
		helper(s, i, i + 1, res);
	}
}

void helper(string s, int left, int right, int res)
{
	if (left >= 0 && right < s.size() && s[left] == s[right])
	{
		--left;
		--right;
		++res;
	}
}